package leetcode

// https://leetcode.com/problems/longest-palindromic-substring/
type Problem string

// the most useful approach, expand around center.
func LongestPalindromeByExpand(s string) string {
	res := ""
	for i := 0; i < len(s); i++ {
		s1 := palindrome(s, i, i)
		s2 := palindrome(s, i, i+1)
		if len(res) < len(s1) {
			res = s1
		}
		if len(res) < len(s2) {
			res = s2
		}
	}
	return res
}

func palindrome(s string, l, r int) string {
	for l >= 0 && r < len(s) && s[l] == s[r] {
		l--
		r++
	}
	// actual return substring is [l+1, r)
	// because broken condition is s[l] != s[r]
	// when no palindrome substring, it will return empty string
	return s[l+1 : r]
}

// the dynamic programming approach
func LongestPalindromeByDynamic(s string) string {
	length := len(s)
	dp := make([][]bool, length)
	// init base case
	for i := range dp {
		dp[i] = make([]bool, length)
		dp[i][i] = true
	}
	for i := 0; i < length-1; i++ {
		dp[i][i+1] = s[i] == s[i+1]
		dp[i+1][i] = s[i+1] == s[i]
	}
	mx, st := 1, 0
	// range for
	for j := 0; j < length; j++ {
		for i := 0; i < j; i++ {
			if j-i > 1 {
				dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
			}
			if dp[i][j] && mx < j-i+1 {
				mx = j - i + 1
				st = i
			}
		}
	}
	// result
	return s[st : st+mx]
}
